Mary Boleyn sinh ra ở Blickling Hall, vùng Norfolk và lớn lên ở Lâu đài Hever, Kent[2]. Bà là con gái của Thomas Boleyn, Bá tước Wiltshire thứ nhất, nguyên là một nhà ngoại giao giàu có phục vụ triều đình Tudor. Mẹ bà là Elizabeth Howard, con gái lớn nhất của Thomas Howard, Công tước thứ 2 xứ Norfolk, và vì lẽ đó mà Công tước Thomas là cậu ruột của bà.

Không có cứ liệu chính xác nào về ngày và năm sinh của Mary, nhưng chỉ dao động từ năm 1499 đến 1508. Nhiều sử gia nhận định Mary là chị cả trong số 3 người con của Thomas Boleyn[3]. Điều này dựa vào việc Mary được đối xử như con cả trong nhà. Ngoài ra vào năm 1597, cháu của Mary là George Carey đã đòi hỏi quyền kế thừa tước hiệu "Bá tước vùng Ormond" do là hậu duệ của Mary Boleyn - người con cả trong nhà. Theo luật pháp quyền thừa kế quý tộc khi đó, dòng dõi của nữ giới có quyền đòi quyền thừa kế nếu trong trường hợp thiếu vắng dòng nam. Có một minh chứng nữa, việc Mary Boleyn là lớn nhất dựa vào cuộc hôn nhân của bà vào năm 1520 với William Carey, vì theo truyền thống con gái cả sẽ kết hôn trước tiên. Ngoài ra, khi Anne Boleyn được ban tước vị Nữ hầu tước xứ Pembroke, đã được giới thiệu trước triều đình là 「"Một trong những người con của Thomas Boleyn"」, mà không phải "con gái cả" để nhấn mạnh. Hầu hết các sử gia hiện đại công nhận Mary Boleyn là con gái cả trong nhà Boleyn, và đặt năm sinh khoảng năm 1499, hay 1500 mà thôi[4].

Có vẻ như Mary cùng Anne và George đều lớn lên và được giáo dục tại Lâu đài Hever xứ Kent. Khác với Anne, Mary chỉ được chú trọng vào những lĩnh vực cơ bản của một tiểu thư quý tộc khi ấy, bao gồm những lý thuyết tôn giáo cơ bản, quy tắc xã giao cơ bản, bên cạnh là số học, ngữ pháp, đánh vần, đọc và viết. Theo truyền thống gia đình Boleyn, Mary còn học những môn xã giao dành cho phụ nữ khác như khiêu vũ, may vá, quản lý việc nhà và ca hát. Thỉnh thoảng, Mary cũng được dạy săn bắn và cưỡi ngựa[5]. Trong hầu hết thời trẻ, Mary chỉ quanh quẩn ở nước Anh, và đến năm 1514 thì bà cùng em gái Anne đi theo Công chúa Mary sang Pháp, sau khi Thomas Boleyn thành công đưa Mary vào đội ngũ Thị tùng cho công chúa. Sau khi đến Pháp, Mary Tudor trở thành Vương hậu sau khi cưới Louis XII của Pháp, Mary Boleyn do đó trở thành Thị tùng của Vương hậu. Sau vài tuần kết hôn, hầu hết Thị tùng người Anh của Tân Vương hậu đều bị điều đi, chỉ riêng Mary vẫn được giữ lại, có lẽ do khi ấy Sir Thomas Boleyn đang là viên Đại sứ của triều đình Anh tại nước Pháp.